package com.banmao.CarlCamp.Day09;

public class MS0207 {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        // 好像记得
        // 首先求出两个链表各自的长度
        // 再计算两个长度的差值 n，此差值就是快慢指针相差的步长
        // 快指针先走 n 步，然后两个指针一起移动并开始比较
        ListNode curA = headA;
        int lenA = 0;
        while (curA.next != null) {
            curA = curA.next;
            lenA++;
        }

        ListNode curB = headB;
        int lenB = 0;
        while (curB.next != null) {
            curB = curB.next;
            lenB++;
        }

        ListNode fastN, slowN;
        int n = 0;
        if (lenA > lenB) {
            fastN = headA;
            slowN = headB;
            n = lenA - lenB;
        } else {
            fastN = headB;
            slowN = headA;
            n = lenB - lenA;
        }

        // 快指针先走 n 步
        while (n > 0) {
            fastN = fastN.next;
            n--;
        }
        // 快慢指针一起走
        while (fastN != null && slowN != null) {
            if (fastN == slowN) {
                return fastN;
            }
            fastN = fastN.next;
            slowN = slowN.next;
        }
        return null;
    }

    private static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
